package ljl.alg.wangzheng_camp.round1.dp;

/**
 *
 * 这个题这么难吗？半天了！
* */
public class _238_mul_except_self {
    
    /**
     * 我只记着那个声明两个数组的了
     * 其实只声明一个就够了
     *
     * 声明两个数组的反而最简单，最好理解
     * 这个不好想，花了半个小时都没整明白
     *
     * 也没啥难的
     *
     * */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        /*
        * 1      nums1 nums2
        * nums0  1     nums2
        * nums0  nums1 1
        * */
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int r = 1;
        for (int i = n - 1; i >= 0 ; i--) {
            res[i] *= r;
            r *= nums[i];
        }
        return res;
    }
}
